iT邦幫忙

2024 iThome 鐵人賽

DAY 20
0
佛心分享-刷題不只是刷題

圖解LeetCode(入門篇)系列 第 20

圖解LeetCode(入門篇): 101. Symmetric Tree

  • 分享至 

  • xImage
  •  

101. Symmetric Tree

题目描述:

給定一個二元樹的根節點 root,判斷這棵樹是否是對稱的。即檢查該二元樹是否等價於其鏡像。

Example 1:
https://ithelp.ithome.com.tw/upload/images/20240829/20168306GH2traJaxj.jpg

  • Input: root = [1,2,2,3,4,4,3]
  • Output: true

Example 2:
https://ithelp.ithome.com.tw/upload/images/20240829/20168306Nbvt5uQpsE.jpg

  • Input: root = [1,2,2,null,3,null,3]
  • Output: false

解題思路:
這道題目是關於二元樹的實作題,有兩種常見的解法:遞迴法和迭代法。我們先介紹比較直觀的遞迴法來解決這個問題。

遞迴法的思路是通過遞迴來比較二元樹的左子樹和右子樹,檢查它們是否對稱。具體步驟如下:

  1. 檢查節點是否為 null:在遞迴函數中,首先比較兩個節點是否都是 null。如果兩者都是 null,那麼這部分樹是對稱的,返回 true。

  2. 處理一個節點為 null 的情況:接著比較是否只有一個節點為 null 而另一個不是。如果是這種情況,樹就不可能對稱,返回 false。

  3. 比較節點值是否相等:如果兩個節點的值相等,則繼續進行下一步遞迴比較:
    比較左子樹的左節點和右子樹的右節點。
    比較左子樹的右節點和右子樹的左節點。
    遞迴比較子樹:如果上述比較都成立,那麼繼續遞迴比較左右子樹的對應節點。如果所有這些比較都返回 true,那麼整棵樹是對稱的。
    https://ithelp.ithome.com.tw/upload/images/20240829/20168306hXKwRp4yLN.jpg

var isSymmetric = function(root) {
    if (!root) return true;

    function isMirror(t1, t2) {
        if (!t1 && !t2) return true;
        if (!t1 || !t2) return false;
        return (t1.val === t2.val)
            && isMirror(t1.right, t2.left)
            && isMirror(t1.left, t2.right);
    }

    return isMirror(root.left, root.right);
};

時間複雜度:O(n),其中 n 是樹中的節點數量。每個節點只會被訪問一次。
空間複雜度:O(h),其中 h 是樹的高度。遞迴call stack的深度與樹的高度成正比。

迭代法的思路與遞迴法相似,只是將遞迴過程轉換為使用 stack 來進行操作。具體過程如下:

  1. 初始化 stack:首先,將根節點的左右子節點分別 pushstack 中。

  2. 逐一比較節點:接著,從 stack 中取出兩個節點進行比較。如果兩個節點的值相同,則繼續比較它們的子節點。

  3. 處理子節點:在比較子節點時,我們將這兩個節點的左子樹的左節點和右子樹的右節點,以及左子樹的右節點和右子樹的左節點分別 pushstack 中。

  4. 重複過程:這個過程會不斷重複,直到 stack 為空。只要在這個過程中所有對應的節點都相同,我們就可以判斷這棵樹是對稱的。

var isSymmetric = function(root) {
    if (!root) return true;

    const stack = [];
    stack.push(root.left);
    stack.push(root.right);

    while (stack.length > 0) {
        const right = stack.pop();
        const left = stack.pop();

        if (!left && !right) continue;
        if (!left || !right) return false;
        if (left.val !== right.val) return false;

        // Push left's left and right's right
        stack.push(left.left);
        stack.push(right.right);

        // Push left's right and right's left
        stack.push(left.right);
        stack.push(right.left);
    }

    return true;
};

時間複雜度:O(n),其中 n 是樹中的節點數量。每個節點都會被訪問一次。
空間複雜度:O(h),其中 h 是樹的高度。stack 的深度取決於樹的高度,在最壞的情況下,stack 的大小可能達到樹的高度。

總結:
這道題目可以歸類為「recursion」和「stack」這兩個分類。這題與上一題 100. Same Tree 的解法幾乎相似,建議讀者可以對這兩題進行比較。

在練習 LeetCode 時,建議首先仔細觀察題目,然後嘗試自己解題。如果遇到困難,可以先參考一些圖解或提示,再試著自己撰寫解答。最後,才是直接查看解答。然而,即使知道了解答,仍應該在不依賴解答的情況下,在 LeetCode 網站上練習撰寫正確的程式碼並成功提交(submit)。這樣可以幫助你鞏固所學,提升解題能力。


上一篇
圖解LeetCode(入門篇): 100. Same Tree
下一篇
圖解LeetCode(入門篇): 104. Maximum Depth of Binary Tree
系列文
圖解LeetCode(入門篇)30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言